1. Field
The present invention generally relates to rule management systems and specifically to a method and a system for detecting missing rules with most general conditions in a rule project having a given scope with a fixed number of objects of a given type.
2. Description of the Related Art
Business Rule Management (BRM) technology relates to the area of decision-making automation in business problems such as loan approval, insurance claim processing or customer fidelity programs. Respective Business Rule Management Systems (BRMS) are implemented to work with rule projects. BRMS allow rule edition in a controlled natural-like language, which makes it easy to use without specific knowledge on generating rules. The rules can be kept in different versions in a rule repository. The BRMS further allows the execution of the rules by a rule engine, which also performs a rule analysis for detecting conflicting rules, redundant rules, and missing rules. Another feature is rule validation by test and simulation.
Business rules are a convenient way to represent decision-making policies which are making decisions depending on given cases. A case usually consists of a combination of features and a decision may be a combination of elementary choices. A business rule makes a decision by applying an action to a given case. A business rule cannot handle all cases, but only those that satisfy a condition. A business rule thus consists of a condition, which usually is a combination of tests, and an action, which may consist of a sequence of elementary steps. As a business rule treats only certain cases, it defines only a part of the whole decision making process. Further business rules are needed to make a decision for the remaining cases. If the given business rules are making a decision for each relevant case, then such a collection of rules is complete. Otherwise, the rules will not treat every case and further rules need to be added to make the rules complete.
Missing rules arise due to unforeseen interactions between the tests of the existing rules, which may complement each other on certain dimensions but leave gaps on other dimensions. The detection of the conditions of the missing rules is a difficult task as not all dimensions are relevant. If irrelevant conditions are included in missing rules, the rules will be more verbose, less concise and, more importantly, the number of missing rules will be increased in a significant way. Ideally, a missing rule should be as general as possible, i.e. have a minimal set of tests and should not be subsumed by other missing rules.
A close examination of the state-of-the-art established that there is no general exact method for detecting most general missing rules (MGMRs). Existing methods for completeness analysis of BRMS are able to identify missing rules in decision tables of a regular form, but are neither able to transform these missing rules into the most general form, nor to achieve these tasks for arbitrary decision tables and arbitrary business rule projects. Indeed, they handle the simple case where each expression of the decision table has a partitioning of its domain into a finite set of sub-domains or ranges. Each cell in the decision table either has a “don't care” condition or it tests whether its expression belongs to one of the sub-domains. As the sub-domains do not overlap, two different tests concerning the same expression cannot be both true. Moreover, the rules of such a decision table are organized in a tree-like manner by merging cells that have the same test and the same parent cell.
The completeness analyzer described in U.S. Pat. No. 7,020,869 identifies missing branches in this tree, but is not capable of transforming these branches into a reduced number of missing rules by replacing irrelevant tests by don't care values. Indeed, it has to apply the inverse operation, namely to expand existing “don't care” cells by duplicating sub-trees before being able to perform the completeness analysis. Moreover, this method is insufficient to handle decision tables with overlapping tests or to find missing cases in arbitrary business rule projects where rules differ in their scope, i.e. the number and types of the object they are matching. U.S. Pat. No. 5,259,066 provides a method for constructing consistent and complete rule bases and for revealing missing rules, but is limited to decision tables as well.
The before-mentioned methods achieve the completeness analysis by exploiting properties of the chosen representation (e.g. missing branch in a tree), but do not provide the necessary enginery for bringing missing rules into a most general form. Similar remarks hold for missing rule detection in binary decision diagrams (see U.S. Pat. Nos. 7,058,910, 6,965,887, and 7,188,091).
A previous patent application (Ser. No. 12/898,359 entitled “Satisfiability For Detecting Missing Cases In Incomplete Business Rules Projects” of the same inventor) shows how to find missing cases and missing case families of a fixed scope, i.e. of a fixed number of objects of given types, for unrestricted rule projects. It provides methods for handling complex interactions between rules, but not for generalizing the missing cases into most general missing rules.
Known methods on rule compression and rule learning are able to generalize a set of missing cases into missing rules, but achieve this with a limited accuracy only and do not guarantee that the rules are in a most general form (see, for example, http://openrules.com/RuleCompressor.htm and http://openrules.com/RuleLearner.htm). The same remark holds for data mining methods (such as U.S. Pat. No. 5,724,573 and U.S. patent application publication no. 2002/0049720 A1). Other learning methods such as explanation-based generalization are able to learn rule-like concept descriptions which are accurate. Those methods prove a target property for a given example and then generalize the proof in order to extract a rule. They cannot be directly applied to missing rule generalization as no target property is given for this problem. Moreover, if the proof is not optimal and uses parts of the example description that other proofs are not using, then the resulting rule is not in a most general form.